package lanQiaoBei.数据结构.kmp;
import java.io.*;
/*
*字符串匹配以及kmp加速
* 给定一个需要匹配的字符串字符串p
* 和一大段字符串s
* 输入格式：
* n
* aba(p)
* m
* ababab(s)
* */
public class P1 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static int N=10010,M=100010;
    static int n,m;
    static char[]p=new char[N],s=new char[M];
    static int[]ne=new int[N];
    static void scan()throws Exception{
           n=Integer.parseInt(br.readLine());
           br.read(p,1,n);
           br.readLine();
           m=Integer.parseInt(br.readLine());
           br.read(s,1,m);
    }
    //暴力做法
    static void baoLi(){
           for(int i=1;i<=m;i++){
              int p1=i,p2=1;
              boolean flag=true;
              while(p1<=m&&p2<=n){
                    if(s[p1]!=p[p2]){
                        flag=false;
                        break;
                    }
                    p1++;
                    p2++;
              }
              if(flag&&p2==n) System.out.print(i+" ");
           }
    }
    static void kmp(){
           //求next的过程
           for(int i=2,j=0;i<=n;i++){
               while(j>0&&p[i]!=p[j+1])j=ne[j];
               if(p[i]==p[j+1])j++;
               ne[i]=j;
           }
           for(int i=1;i<=n;i++)
           {
               System.out.print(ne[i]+" ");

           }
           System.out.println();
           //匹配过程
           for(int i=1,j=0;i<=m;i++){
               while(j>0&&s[i]!=p[j+1])j=ne[j];
               if(s[i]==p[j+1])j++;
               if(j==n){
                   System.out.print(i-n+" ");
                   j=ne[j];
               }
           }
    }
    public static void main(String[] args)throws Exception{
           scan();
           //暴力枚举
           //baoLi();
          //kmp
          kmp();

    }
}
